#include "SearchBinary.h"
#include <string>



void test1()  //二叉排序树
{
	 //1、查找
	// 2、去重
	// 3、排序 + 去重
	//由于最坏情况下会退化，因此其增删查改时间复杂度为O(N)
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	BSTree<int> t;
	for (auto e : a) 
	{
		t.Insert(e);
	}

	t.Insert(16);
	t.Insert(4);

	t.Inorder();
	cout << endl;

	t.Erase(3);
	t.Inorder();
	cout << endl;

	t.Erase(4);
	t.Inorder();
	cout << endl;
}



void test2()
{
	// 输入单词，查找单词对应的中文翻译
	keyValue::BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("left", "左边、剩余");
	dict.Insert("right", "右边");
	dict.Insert("sort", "排序");
	// 插入词库中所有单词
	string str;
	while (cin >> str)
	{
		auto ret = dict.Find(str);
		if (ret == nullptr)
		{
			cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
		}
		else
		{
			cout << str << "中文翻译:" << ret->_value << endl;
		}
	}
}

void test3()
{
	// 统计水果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
	"苹果", "香蕉", "苹果", "香蕉" };
	keyValue::BSTree<string, int> countTree;
	for (const auto& str : arr)
	{
		// 先查找水果在不在搜索树中
		// 1、不在，说明水果第一次出现，则插入<水果, 1>
		// 2、在，则查找到的节点中水果对应的次数++
		//BSTreeNode<string, int>* ret = countTree.Find(str);
		auto ret = countTree.Find(str);
		if (ret == NULL)
		{
			countTree.Insert(str, 1);
		}
		else
		{
			ret->_value++;
		}
	}
	countTree.InOrder();
}

void test4()
{
	keyValue::BSTree<string, string> dict;
	dict.Insert("string", "字符串");
	dict.Insert("tree", "树");
	dict.Insert("left", "左边、剩余");
	dict.Insert("right", "右边");
	dict.Insert("sort", "排序");
	keyValue::BSTree<string, string> copy(dict);

}


int main()
{
	test1();
	//test2();

	//test3();

	//test4(); 

	return 0;
}